[POJ 3469] Dual Core CPU

原题链接:[POJ 3469] Dual Core CPU

原题大意:给定给一个有两个核的CPU,一共要执行$n$个模块,每个模块$i$在A核上运行的时间是$A_i$.在B核上的时间是$B_i$.给出$M$对之间需要进行数据交换的模块组合$(a,b)$.如果两者在同一核上运行则不需要额外代价,否则需要额外的$w_i$的时间.
数据范围:
$1 \leq n \leq 20000$
$1 \leq m \leq 200000$

思路

整个问题可以这么考虑:把所有的模块都分成两堆,分别在A核上执行或者在B核上执行,那么实际上就是根据代价求一个最小割,先把割是什么确定下来.
源点是$s$,汇点是$t$.把在A核上执行的集合记作S,在B核上执行的集合记作T.那么$s-t$割里对应过来就是S包含s,T包含t.这样两个集合就划分完毕了.最后总的代价就是$\sum\limits_{i\in S}A_i+\sum\limits_{i\in T}B_i+\sum\limits_{a_i\in S,b_i\in T}w_i+\sum\limits_{a_i\in T,b_i\in S}w_i$对于最小割来说,最小化的是容量,因此把割的容量作为代价再建图就可以解决了.考虑具体怎么建图:
对于表达式里的$\sum\limits_{i\in S}A_i$.就是说明属于$S$集合的某个点$i$要在A核上运行,产生了$A_i$的代价.对于割来说,你选了A就不能选B,这是一个断开的关系,因此是从点$i$连向汇点t,容量就是代价.最小割问题求解的是:让s到t没有一个路径,最少删边的容量之和.就是这个边应该是两个集合之间的连边,他不是集合内部的.对于$\sum\limits_{i\in T}B_i$同理让源点连向$i$即可.
对于剩下两个两个点的关系,直接连边即可.当这这两个集合之间的所有边都被删掉之后,自然就不联通了.而最小割-最大流定理在这里可以可以继续转化问题,把求解最小割的问题变成一个求解最大流的问题.因此只要在建立的新图上求最大流就是答案了.

代码

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e6+7,M = 1e6+7,INF = 1 << 29;
int edge[M],succ[M],cap[M],ver[N],idx = 1;
int n,m,s,t,d[N],pre[N];
ll incf[N],maxflow;
queue<int> q;
void add(int u,int v,int w)
{
	edge[++idx] = v;
	cap[idx] = w;
	succ[idx] = ver[u];
	ver[u] = idx; 
	
	edge[++idx] = u;
	cap[idx] = 0;
	succ[idx] = ver[v];
	ver[v] = idx;
}
bool bfs()
{
	memset(d,0,sizeof d);
	while(q.size())	q.pop();
	q.push(s);d[s] = 1;
	while(!q.empty())
	{
		int u = q.front();q.pop();
		for(int i = ver[u];i;i = succ[i])
		{
			int v = edge[i];
			if(cap[i] && !d[v])
			{
				q.push(v);
				d[v] = d[u] + 1;
				if(v == t)	return 1;
			}
		}
	}
	return 0;
}
int dinic(int u,int flow)
{
	if(u == t)	return flow;
	int rest = flow,k,i;
	for(int i = ver[u];i && rest;i = succ[i])
	{
		int v = edge[i];
		if(cap[i] && d[v] == d[u] + 1)
		{
			k = dinic(v,min(rest,cap[i]));
			if(!k)	d[v] = 0;
			cap[i] -= k;
			cap[i ^ 1] += k;
			rest -= k;
		}
	}
	return flow - rest;
}
int main()
{
	scanf("%d%d",&n,&m);
	s = 0;t = n + 1;
	for(int i = 1;i <= n;++i)
	{
		int a,b;scanf("%d%d",&a,&b);
		add(i,t,a);
		add(s,i,b);
	}
	for(int i = 0;i < m;++i)
	{
		int u,v,w;scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);add(v,u,w);
	}
	int flow = 0;
	while(bfs())	
		while(flow = dinic(s,INF)) 
			maxflow += flow;
	printf("%lld",maxflow);
    return 0;
}